package com.shuang.dp40;

class Solution {
    //动态规划
    public int countSubstrings(String s) {
        char[] chars = s.toCharArray();
        int len = chars.length;

        //dp[i][j]表示 范围[i,j]的字符子串是否是回文子串
        boolean[][] dp = new boolean[len][len];
        //记录结果
        int result = 0;

        //递推公式
        //字符子串的 i和j 的位置的字符相同的话 就看 [i,j]范围内往前一格（[i+1, j-1])的范围内的是否是回文的即可
        // 情况一：下标i 与 j相同，同一个字符例如a，当然是回文子串
        // 情况二：下标i 与 j相差为1，例如aa，也是回文子串
        // 情况三：下标：i 与 j相差大于1的时候，例如cabac，此时s[i]与s[j]已经相同了，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看dp[i + 1][j - 1]是否为true。

        //初始化，一定先初始化都为false然后一点点填充才对

        //遍历顺序，当前位置是由当前位置的左下位置得到的所以 从下到上 从左到右遍历（j一定是大于等于i的）
        for (int i = len - 1; i >= 0; i--) {
            for (int j = i; j < len; j++) {
                if (chars[i] == chars[j]) {
                    if (j - i <= 1) { // 情况一 和 情况二
                        result++;
                        dp[i][j] = true;
                    } else if (dp[i + 1][j - 1]) { //情况三
                        result++;
                        dp[i][j] = true;
                    }
                }
            }
        }
        return result;
    }
}